package com.mianshi;

/**
 * n皇后
 */
public class bole4 {
    int ans = 0;
    public int queens (int n) {
        // write code here
        dfs(n,0,0,0,0);
        return ans;
    }

    public void dfs(int n, int row, int column, int n1, int n2){
        if(row == n){
            ans++;
            return;
        }
        int positions = ((1<<n)-1)&(~(column|n1|n2));
        while(positions != 0){
            int p = positions&(-positions);
            positions &= (positions-1);
            dfs(n,row+1,column|p,(n1|p)<<1,(n2|p)>>1);
        }
    }
}
